package _02_链表;

public class _876_链表的中间结点 {

    // 计数法
    public ListNode middleNode1(ListNode head) {
        ListNode newHead = head;
        // 计数
        int count = 1;
        while ((newHead = newHead.next) != null) {
            count++;
        }
        // 寻求中间值
        int avg = count >> 1;
        newHead = head;
        while (avg-- > 0) {
            newHead = newHead.next;
        }
        return newHead;
    }

    // 快慢指针法
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
